Knapsack.java

packagesection19_DynamicProgramming;

publicclassKnapsack {

publicstaticvoidmain(String[] args) {
int[] weight = { 1, 3, 4, 5 };
int[] price = { 1, 4, 5, 7 };
intbagCapacity = 7;
intvirtualIndex = 0;

int[][] strg = newint[weight.length][bagCapacity + 1];

System.out.println(knapsack01Rec(weight, price, bagCapacity, virtualIndex)); // 9
System.out.println(knapsackTopDown(weight, price, bagCapacity, virtualIndex, strg)); // 9
System.out.println(knapsackBottomUpDP(weight, price, bagCapacity)); // 9

System.out.println("\ntesting large inputs...\n" + "");

intn = 1000;
int[] wt = newint[n];
int[] p = newint[n];
intcap = 70;
for (inti = 0; i < n; i++) {
wt[i] = i + 1;
p[i] = i + 2;
 }

// using DP
int[][] storage = newint[wt.length][cap + 1];

longstart = System.currentTimeMillis();
// System.out.println(knapsack01Rec(wt, p, cap, 0));
System.out.println(knapsackTopDown(wt, p, cap, 0, storage));
longend = System.currentTimeMillis();
System.out.println("time taken by top down: " + (end - start) + " msec");

start = System.currentTimeMillis();
System.out.println(knapsackBottomUpDP(wt, p, cap));
end = System.currentTimeMillis();
System.out.println("time taken by bottom up: " + (end - start) + " msec");

 }

/*
 * Big O analysis shortcut for recursive solution-
 * 
 * time = no. of function frames * time taken by 1 function frame
 * 
 * no. of function frame = total calls ^ (recursion tree height)
 */

// O(2^n) Time, n = total items in bag
publicstaticintknapsack01Rec(int[] weight, int[] price, intcapacity, intvidx) {
/*
 * 1. if no item left
 * 
 * 2. if current capacity is less than item weight to be included
 */
if (vidx == weight.length || capacity < weight[vidx]) {
return0;
 }

// exclude item
intexcludeProfit = knapsack01Rec(weight, price, capacity, vidx + 1);
// include item
intincludeProfit = price[vidx] + knapsack01Rec(weight, price, capacity - weight[vidx], vidx + 1);

intprofit = Math.max(excludeProfit, includeProfit);

returnprofit;
 }

publicstaticintknapsackTopDown(int[] weight, int[] price, intcapacity, intvidx, int[][] storage) {

if (vidx == weight.length || capacity == 0) {
return0;
 }
if (storage[vidx][capacity] != 0) {
returnstorage[vidx][capacity];
 }

intexcludeProfit = knapsackTopDown(weight, price, capacity, vidx + 1, storage);

intincludeProfit = 0;

if (capacity >= weight[vidx])
includeProfit = price[vidx] + knapsackTopDown(weight, price, capacity - weight[vidx], vidx + 1, storage);

intprofit = Math.max(excludeProfit, includeProfit);
storage[vidx][capacity] = profit;

returnprofit;
 }

// O(NM) Time, N is total items, M is total capacity | O(NM) Space
publicstaticintknapsackBottomUpDP(int[] weight, int[] price, intcapacity) {
int[][] storage = newint[weight.length + 1][capacity + 1];

// filling bottom up, left to right
for (introw = weight.length - 1; row >= 0; row--) {

for (intcol = 1; col <= capacity; col++) {

intexclude = storage[row + 1][col];

intinclude = 0;
if (col >= weight[row])
include = storage[row + 1][col - weight[row]] + price[row];

intans = Math.max(exclude, include);

storage[row][col] = ans;
 }
 }

returnstorage[0][capacity];
 }
}